package com.algorithm.liyc.practice;

import com.algorithm.liyc.entity.ListNode;

/**
 * 翻转链表
 * 反转一个单链表。
 *
 * @author Liyc
 * @date 2023/11/23 15:57
 **/

public class Solution9 {
    /**
     * 双指针
     * ● 时间复杂度: O(n)
     * ● 空间复杂度: O(1)
      */
    public ListNode reverseList1(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while (cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    /**
     * 递归
     * ● 时间复杂度: O(n), 要递归处理链表的每个节点
     * ● 空间复杂度: O(n), 递归调用了 n 层栈空间
      */
    public ListNode reverseList2(ListNode head) {
        return reverse(null,head);
    }

    public ListNode reverse(ListNode pre, ListNode cur){
        if (cur == null) return pre;
        ListNode tmp = null;
        tmp = cur.next;
        cur.next = pre;
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur,tmp);
    }


    /**
     * 从后向前递归
     * ● 时间复杂度: O(n)
     * ● 空间复杂度: O(n)
      */
    public ListNode reverseList3(ListNode head) {
        // 边缘条件判断
        if(head == null) return null;
        if (head.next == null) return head;

        // 递归调用，翻转第二个节点开始往后的链表
        ListNode last = reverseList3(head.next);
        // 翻转头节点与第二个节点的指向
        head.next.next = head;
        // 此时的 head 节点为尾节点，next 需要指向 NULL
        head.next = null;
        return last;
    }

}
